package leetcode.ge100;

import java.util.HashMap;

class Node {
	int key;
	int val;
	Node pre;
	Node next;

	Node(int key, int val) {
		this.key = key;
		this.val = val;
	}

	@Override
	public String toString() {
		return "Node [key=" + key + ", val=" + val + "]";
	}

}

public class LRUCache {

	private int size;

	private HashMap<Integer, Node> map;

	private Node head, tail;

	private int amount;

	public LRUCache(int capacity) {
		this.size = capacity;
		this.map = new HashMap<Integer, Node>(this.size);
	}

	public int get(int key) {
		Node node = map.get(key);
		if (node == null)
			return -1;
		goTop(node);
		return node.val;
	}

	public void put(int key, int value) {
		if (map.containsKey(key)) {
			update(key, value);
		} else if (amount == size) {
			remove();
			set(key, value);
		} else {
			amount++;
			set(key, value);
		}

	}

	private void remove() {
		map.remove(tail.key);
		tail = tail.pre;
		tail.next = null;

	}

	private void set(int key, int value) {
		Node node = new Node(key, value);
		map.put(key, node);
		if (amount == 1) {
			head = node;
			tail = node;
		}
		goTop(node);
	}

	private void update(int key, int value) {
		Node node = map.get(key);
		node.val = value;
		goTop(node);
	}

	private void goTop(Node node) {
		if (node.next == null && node.pre == null) {// 新插入的节点
			link(node, head);
			head = node;
		} else if (node == head) {// 本来就在头部
			return;
		} else if (node == tail) {// 本来在尾部且不在头部
			tail = node.pre;
			tail.next = null;

			link(node, head);
			head = node;
			node.pre = null;
		} else {// 本来在中间部位
			link(node.pre, node.next);
			link(node, head);
			head = node;
			node.pre = null;
		}
	}

	private void link(Node node, Node node2) {
		node.next = node2;
		node2.pre = node;
	}

	public static void main(String[] args) {
		LRUCache lru = new LRUCache(2);
		lru.put(1, 1);
		lru.put(2, 2);
		lru.get(1);
		lru.put(3, 3);
		lru.get(2);
		lru.put(4, 4);
		lru.get(1);
		lru.get(3);
		lru.get(4);
	}

}
